//============================================================================
// Name        : metop.cpp
// Author      : Santiago Iturriaga
// Version     :
// Copyright   : 
// Description :
//============================================================================

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <queue>
#include <math.h>
#include <cmath>
#include <assert.h>
#include <omp.h>

#include "TSPNode.h"
#include "TSPCostMatrix.h"
#include "Solution.h"
#include "TSPPath.h"
#include "TSPPathMatrix.h"
#include "GlobalDefs.h"
#include "Graph.h"
#include "IntMatrix.h"
#include "YenTopKShortestPathsAlg.h"
#include "DijkstraShortestPathAlg.h"

using namespace std;

/*
 * Carga los nodos de la instancia de TSP a utilizar.
 */
int load_instance(const string &instance_file_path, vector<TSPNode> &nodos) {
	ifstream instance_file(instance_file_path.data());
	if (!instance_file) {
		puts("[ERROR] Input file not found.");
		return EXIT_FAILURE;
	}

	cout << "[INFO] Leyendo archivo...";

	{
		bool coord_section_started = false;
		string linea;
		int coord_id;
		double coord_x, coord_y;

		while (instance_file.good()) {
			if (!coord_section_started) {
				instance_file >> linea;

				// Aún no comenzó la sección de coordenadas.
				// Leo resto de los datos.
				if (linea.compare("NODE_COORD_SECTION") == 0) {
					// A continuación aparecen las coordenadas
					// en el texto.
					coord_section_started = true;
				}
			} else {
				instance_file >> linea;

				if (linea != "EOF") {
					coord_id = atoi(linea.data());
					instance_file >> coord_x;
					instance_file >> coord_y;

					TSPNode node(nodos.size(), coord_id, coord_x, coord_y,
							false);
					nodos.push_back(node);
				}
			}
		}
	}

	cout << "\t\t<OK>" << endl;

	return EXIT_SUCCESS;
}

/*
 * Calcula la distancia euclidiana 2D entre dos nodos.
 */
double calcular_distancia(const TSPNode *node_1, const TSPNode *node_2) {
	double x_pow = pow(node_1->get_coord_x() - node_2->get_coord_x(), 2.0);
	double y_pow = pow(node_1->get_coord_y() - node_2->get_coord_y(), 2.0);
	return sqrt(x_pow + y_pow);
}

/*
 * Calcula la distancia euclidiana 2D entre un par de coordenadas y un nodo.
 */
double calcular_distancia(double coord_x, double coord_y, const TSPNode *node) {
	double x_pow = pow(coord_x - node->get_coord_x(), 2.0);
	double y_pow = pow(coord_y - node->get_coord_y(), 2.0);
	return sqrt(x_pow + y_pow);
}

/*
 * Genera un número al azar en el rango [min,max]
 */
double random(double min, double max) {
	assert(max > min);

	double diff;
	diff = max - min;

	double random_0_1;
	random_0_1 = rand() / double(RAND_MAX);

	double random_min_max;
	random_min_max = (random_0_1 * diff) + min;

	return random_min_max;
}

/*
 * Genera un número entero al azar en el rango [min,max]
 */
int random_int(int min, int max) {
	int value = rand();
	int range = (max - min);
	int order = value % (range + 1);
	return (min + order);
}

/*
 * Calcula los costos entre los nodos según alguna distancia (e.g. la distancia euclidiana),
 * y carga los costos calculados en la matriz de costos.
 */
int calculate_costs(const vector<TSPNode> &nodes, TSPCostMatrix &costs) {
	double cost;
	const TSPNode *current_node;
	const TSPNode *destination_node;

	double min_cost, max_cost;
	min_cost = INFINITY;
	max_cost = 0.0;

	// Primero calculo las distancias de los nodos que no son de Stainer.
	for (unsigned int current_node_index = 0; current_node_index < nodes.size(); current_node_index++) {

		for (unsigned int destination_node_index = 0; destination_node_index
				< current_node_index; destination_node_index++) {

			current_node = &(nodes[current_node_index]);
			destination_node = &(nodes[destination_node_index]);

			if ((!current_node->is_stainer_node())
					&& (!destination_node->is_stainer_node())) {

				// Ninguno de los nodos es de Stainer. Utilizo la distancia
				// Euclidiana normal.
				cost = calcular_distancia(current_node, destination_node);
				costs.set_cost(current_node_index, destination_node_index, cost);

				if (cost < min_cost)
					min_cost = cost;
				if (cost > max_cost)
					max_cost = cost;
			}
		}
	}

	// Ahora calculo (invento) las distancias a los nodos de Stainer.
	cout << "[INFO] Min cost = " << min_cost << endl;
	cout << "[INFO] Max cost = " << max_cost << endl;

	double q_constant;
	q_constant = 1.0 / 8.0;

	for (unsigned int current_node_index = 0; current_node_index < nodes.size(); current_node_index++) {

		for (unsigned int destination_node_index = 0; destination_node_index
				< current_node_index; destination_node_index++) {

			current_node = &(nodes[current_node_index]);
			destination_node = &(nodes[destination_node_index]);

			if ((current_node->is_stainer_node())
					|| (destination_node->is_stainer_node())) {

				if ((current_node->get_coord_x() > 0)
						&& (current_node->get_coord_y() > 0)
						&& (destination_node->get_coord_x() > 0)
						&& (destination_node->get_coord_y() > 0)) {
					// Ambos nodos de Stainer tienen coordenadas.
					// Utilizo la distancia Euclidiana normal.
					cost = calcular_distancia(current_node, destination_node);
					costs.set_cost(current_node_index, destination_node_index,
							cost);
				} else {
					// Al menos uno de los nodos es de Stainer.

					// ==================================================
					// Invento un costo para los nodos de Stainer.
					// ver Robledo05 (¿pagina 99?).
					// ==================================================
					cost = random(min_cost, max_cost) * q_constant;
					costs.set_cost(current_node_index, destination_node_index,
							cost);
				}
			}
		}
	}

	return EXIT_SUCCESS;
}

/*
 * Agrega nodos de Stainer a la lista de nodos.
 */
int generate_stainer_nodes(vector<TSPNode> &nodes, unsigned int stainer_nodes,
		bool mantener_desigualdad_triangular) {
	double max_x = 0.0;
	double min_x = INFINITY;
	double max_y = 0.0;
	double min_y = INFINITY;

	if (mantener_desigualdad_triangular) {
		for (unsigned int i = 0; i < nodes.size(); i++) {
			if (nodes[i].get_coord_x() > max_x) {
				max_x = nodes[i].get_coord_x();
			}

			if (nodes[i].get_coord_x() < min_x) {
				min_x = nodes[i].get_coord_x();
			}

			if (nodes[i].get_coord_y() > max_y) {
				max_y = nodes[i].get_coord_y();
			}

			if (nodes[i].get_coord_y() < min_y) {
				min_y = nodes[i].get_coord_y();
			}
		}
	}

	TSPNode *node;
	for (unsigned int i = 0; i < stainer_nodes; i++) {
		if (mantener_desigualdad_triangular) {
			node = new TSPNode(nodes.size(), nodes.size() + 1, min_x + (random(
					0.0, 1.0) * (max_x - min_x)), min_y + (random(0.0, 1.0)
					* (max_y - min_y)), true);
		} else {
			node = new TSPNode(nodes.size(), nodes.size() + 1, -1, -1, true);
		}
		nodes.push_back(*node);
	}

	return EXIT_SUCCESS;
}

TSPPath* buscar_camino_en_sol(const Solution &sol, const int nodo_i,
		const int nodo_j) {
	Graph g(sol);

	BaseVertex* vertex_i = g.get_vertex(nodo_i);
	BaseVertex* vertex_j = g.get_vertex(nodo_j);

	assert(vertex_i != NULL);
	assert(vertex_j != NULL);

	BasePath* shortestPath;
	//	YenTopKShortestPathsAlg yenAlg(g);
	//	shortestPath = yenAlg.get_shortest_path(vertex_i, vertex_j);
	DijkstraShortestPathAlg dijk(&g);
	shortestPath = dijk.get_shortest_path(vertex_i, vertex_j);
	assert(shortestPath != NULL);

	BaseVertex* yenVertex;
	TSPPath* tspPath;
	tspPath = new TSPPath(sol.get_costMatrix());

	for (int vertex_index = 0; vertex_index < shortestPath->length(); vertex_index++) {
		yenVertex = shortestPath->GetVertex(vertex_index);

		if (vertex_index == 0) {
			tspPath->add_initial_node(yenVertex->getID());
		} else {
			tspPath->add_node(yenVertex->getID());
		}
	}

	return tspPath;
}

void buscar_k_caminos(const vector<unsigned int> &nodos_fijos,
		TSPCostMatrix &costs, const Solution &sol, TSPPathMatrix &P,
		const int nodo_i_index, const int nodo_j_index, const int k_mejores,
		vector<TSPPath> &Lp) {

	Graph g(nodos_fijos, costs, sol, P);
	YenTopKShortestPathsAlg yenAlg(g, g.get_vertex(nodos_fijos[nodo_i_index]),
			g.get_vertex(nodos_fijos[nodo_j_index]));

	TSPPath* tspPath;
	vector<BasePath*> yenPathFound;
	BasePath* yenPath;
	BaseVertex* yenVertex;

	for (unsigned int k = 0; (k < K_CAMINOS_MAS_CORTOS) && yenAlg.has_next(); k++) {
		yenPath = yenAlg.next();
		yenPathFound.push_back(yenPath);

		tspPath = new TSPPath(costs);

		for (int vertex_index = 0; vertex_index < yenPath->length(); vertex_index++) {
			yenVertex = yenPath->GetVertex(vertex_index);

			if (vertex_index == 0) {
				tspPath->add_initial_node(yenVertex->getID());
			} else {
				tspPath->add_node(yenVertex->getID());
			}
		}

		Lp.push_back(*tspPath);
		delete tspPath;
	}

	for (unsigned int i = 0; i < yenPathFound.size(); i++) {
		delete yenPathFound[i];
	}
}

void update_matrix(const vector<unsigned int> &nodos_fijos,
		const Solution &sol, TSPPathMatrix &P, IntMatrix &M, const TSPPath* p,
		const unsigned int nodo_i_index, const unsigned int nodo_j_index) {

	for (unsigned int nodo_t_index = 0; nodo_t_index < p->get_size(); nodo_t_index++) {
		unsigned int nodo_t;
		nodo_t = p->get_node_at(nodo_t_index);

		bool es_nodo_fijo = false;
		unsigned int nodo_t_index = 0;
		for (unsigned int nodo_fijo_index = 0; (nodo_fijo_index
				< nodos_fijos.size()) && (!es_nodo_fijo); nodo_fijo_index++) {
			es_nodo_fijo = (nodo_t == nodos_fijos[nodo_fijo_index]);
			nodo_t_index = nodo_fijo_index;
		}

		// Línea 1: nodo_p existe en el camino p y también es un nodo fijo.
		if (es_nodo_fijo) {
			if ((nodo_t != nodos_fijos[nodo_i_index]) && (nodo_t
					!= nodos_fijos[nodo_j_index])) {
				{
					// Línea 2
					if (M.get(nodo_t_index, nodo_j_index) == 2) {
						assert(P.get_path(nodo_t_index,nodo_j_index) == NULL);

						TSPPath *aux;
						aux
								= new TSPPath(*p, nodo_t,
										nodos_fijos[nodo_j_index]);
						P.set_path(nodo_t_index, nodo_j_index, aux);

						if (DEBUG) {
							cout
									<< "[DEBUG] <Update_Matrix> (1) Se agrega el path ";
							aux->show();
							cout << endl;
						}

						if (M.get(nodo_i_index, nodo_j_index) == 1) {
							M.set(nodo_t_index, nodo_j_index, M.get(
									nodo_t_index, nodo_j_index) - 1);
						} else {
							M.set(nodo_t_index, nodo_j_index, M.get(
									nodo_t_index, nodo_j_index) - 2);
						}
					}
				}
				{
					// Línea 6
					if (M.get(nodo_i_index, nodo_t_index) == 2) {
						assert(P.get_path(nodo_i_index,nodo_t_index) == NULL);

						TSPPath *aux;
						aux
								= new TSPPath(*p, nodos_fijos[nodo_i_index],
										nodo_t);
						P.set_path(nodo_i_index, nodo_t_index, aux);

						if (DEBUG) {
							cout
									<< "[DEBUG] <Update_Matrix> (2) Se agrega el path ";
							aux->show();
							cout << endl;
						}

						if (M.get(nodo_i_index, nodo_j_index) == 1) {
							M.set(nodo_i_index, nodo_t_index, M.get(
									nodo_i_index, nodo_t_index) - 1);
						} else {
							M.set(nodo_i_index, nodo_t_index, M.get(
									nodo_i_index, nodo_t_index) - 2);
						}
					}
				}
				{
					unsigned int nodo_tt_index = 0;
					for (nodo_tt_index = 0; nodo_tt_index < nodos_fijos.size(); nodo_tt_index++) {
						unsigned int nodo_tt;
						nodo_tt = nodos_fijos[nodo_tt_index];

						if ((nodo_tt != nodos_fijos[nodo_i_index]) && (nodo_tt
								!= nodos_fijos[nodo_j_index])) {
							if (M.get(nodo_t_index, nodo_tt_index) == 2) {

								bool tt_es_nodo_path = false;
								tt_es_nodo_path = p->contains_node(nodo_tt);

								if (!tt_es_nodo_path) {
									if ((M.get(nodo_i_index, nodo_tt_index) < 2)
											|| (M.get(nodo_j_index,
													nodo_tt_index) < 2)) {

										TSPPath* shortestPath; // camino más corto desde t a tt.
										shortestPath = buscar_camino_en_sol(
												sol, nodo_t, nodo_tt);
										assert(shortestPath != NULL);
										P.set_path(nodo_t_index, nodo_tt_index,
												shortestPath);

										if (DEBUG) {
											cout
													<< "[DEBUG] <Update_Matrix> (3) Se agrega el path ";
											shortestPath->show();
											cout << endl;
										}

										M.set(nodo_t_index, nodo_tt_index,
												M.get(nodo_t_index,
														nodo_tt_index) - 1);
									}
								}
							}
						}
					}
				}
			}
		}
	}
}

void constphase2_2NS(TSPCostMatrix &costs,
		const vector<unsigned int> &nodos_fijos, Solution &sol) {
	int cant_nodos_fijos = nodos_fijos.size();
	assert(cant_nodos_fijos >= 3);

	if (DEBUG)
		cout << "[DEBUG] Cant. nodos fijos: " << cant_nodos_fijos << endl;

	// Matriz de requerimientos de conexión.
	IntMatrix M(cant_nodos_fijos);
	int cantidad_par_nodos_no_satisfechos = 0;
	for (int i = 0; i < cant_nodos_fijos; i++) {
		for (int j = 0; j < i; j++) {
			if (j < i) {
				M.set(i, j, 2);
				cantidad_par_nodos_no_satisfechos++;
			}
		}
	}

	// Matriz auxiliar de caminos (P).
	TSPPathMatrix P(cant_nodos_fijos);

	// Matriz auxiliar de intentos (A).
	IntMatrix A(cant_nodos_fijos);
	for (int i = 0; i < cant_nodos_fijos; i++) {
		for (int j = 0; j < i; j++) {
			if (j < i) {
				A.set(i, j, 0);
			}
		}
	}

	while (cantidad_par_nodos_no_satisfechos > 0) {
		if (DEBUG)
			cout
					<< "=== COMIENZA ITERACIÓN ============================================"
					<< endl;

		if (DEBUG) {
			cout << "[DEBUG] Cant. par de nodos no satisfechos: "
					<< cantidad_par_nodos_no_satisfechos << endl;
			cout << "[DEBUG] Sorteo de par de nodos entre 1 y "
					<< cantidad_par_nodos_no_satisfechos << endl;
		}

		// Obtengo un par de nodos no satisfechos, aleatoriamente =========================
		int indice_par_nodos_aleatorio = random_int(1,
				cantidad_par_nodos_no_satisfechos);

		if (DEBUG)
			cout << "[DEBUG] Indice par de nodos no satisfechos sorteados: "
					<< indice_par_nodos_aleatorio << endl;

		int indice_par_nodos = 0;
		int nodo_i_index = -1, nodo_j_index = -1;
		for (int i = 0; (i < cant_nodos_fijos) && (indice_par_nodos
				!= indice_par_nodos_aleatorio); i++) {
			for (int j = 0; (j < i) && (indice_par_nodos
					!= indice_par_nodos_aleatorio); j++) {
				if (M.get(i, j) > 0) {
					indice_par_nodos++;

					if (indice_par_nodos == indice_par_nodos_aleatorio) {
						nodo_i_index = i;
						nodo_j_index = j;
					}
				}
			}
		}

		assert(nodo_i_index >= 0);
		assert(nodo_j_index >= 0);
		assert(nodo_i_index < cant_nodos_fijos);
		assert(nodo_j_index < nodo_i_index);

		if (DEBUG)
			cout << "[DEBUG] Nodo aleatorio i: " << nodos_fijos[nodo_i_index]
					<< endl;
		if (DEBUG)
			cout << "[DEBUG] Nodo aleatorio j: " << nodos_fijos[nodo_j_index]
					<< endl;

		// Obtengo los k-caminos más cortos desde i a j ===================================
		vector<TSPPath> Lp; // caminos más cortos desde i a j.
		Lp.clear();

		if (DEBUG) {
			//			cout << "[DEBUG] Matriz P" << endl;
			//			P.show();
			cout << "[DEBUG] Cantidad de caminos: " << P.size() << endl;

			cout << "[DEBUG] Buscando caminos entre "
					<< nodos_fijos[nodo_i_index] << " y "
					<< nodos_fijos[nodo_j_index] << "...";
		}

		buscar_k_caminos(nodos_fijos, costs, sol, P, nodo_i_index,
				nodo_j_index, K_CAMINOS_MAS_CORTOS, Lp);

		if (DEBUG) {
			cout << "<OK>" << endl;

			if (Lp.size() > 0) {
				for (unsigned int x = 0; x < Lp.size(); x++) {
					cout << "[DEBUG] Camino " << x << ": ";
					Lp[x].show();
					cout << endl;
				}
			} else {
				cout << "[DEBUG] No se encontraron caminos!!!" << endl;
			}
		}

		// =================================================================================

		if (Lp.empty()) {
			// No encontré ningún camino entre (i,j). Reseteo los datos de (i,j).
			A.set(nodo_i_index, nodo_j_index, A.get(nodo_i_index, nodo_j_index)
					+ 1);
			M.set(nodo_i_index, nodo_j_index, 2);

			if (P.get_path(nodo_i_index, nodo_j_index) != NULL)
				P.remove_path(nodo_i_index, nodo_j_index);
		} else {
			TSPPath *p = NULL;

			// Si encuentro un camino de costo cero lo selecciono.
			for (unsigned int i = 0; (i < Lp.size()) && (p == NULL); i++) {
				if (sol.get_cost_to_add(Lp[i]) == 0.0) {
					p = &Lp[i];
				}
			}

			// Si no hay caminos de costo cero, selecciono un camino aleatorio.
			if (p == NULL) {
				p = &Lp[random_int(0, Lp.size() - 1)];
			}

			if (DEBUG) {
				cout << "[DEBUG] Path agregado a la solución: ";
				p->show();
				cout << endl;
			}
			sol.add_path(*p);

			if (M.get(nodo_i_index, nodo_j_index) == 2) {
				if (P.get_path(nodo_i_index, nodo_j_index) != NULL)
					P.remove_path(nodo_i_index, nodo_j_index);
				P.set_path(nodo_i_index, nodo_j_index, new TSPPath(*p));
			}
			M.set(nodo_i_index, nodo_j_index, M.get(nodo_i_index, nodo_j_index)
					- 1);

			// [P,M]<-Update_Matrix(Gsol,P,M,p,i,j)
			update_matrix(nodos_fijos, sol, P, M, p, nodo_i_index, nodo_j_index);
		}

		cantidad_par_nodos_no_satisfechos = 0;
		for (int i = 0; i < cant_nodos_fijos; i++) {
			for (int j = 0; j < i; j++) {
				if (j < i) {
					if (M.get(i, j) > 0) {
						//						if (DEBUG) {
						//							cout << "[DEBUG] Matriz requerimientos ("
						//									<< nodos_fijos[i] << "," << nodos_fijos[j]
						//									<< ") = " << M.get(i, j) << endl;
						//						}
						cantidad_par_nodos_no_satisfechos++;
					}
				}
			}
		}
	}
	if (DEBUG)
		cout
				<< "==================================================================="
				<< endl;
}

void calcular_nodos_fijos(const vector<TSPNode> &nodos,
		const TSPCostMatrix &costos, vector<unsigned int> &nodos_fijos,
		double multiplicador) {

	nodos_fijos.clear();

	double centroide_x = 0.0;
	double centroide_y = 0.0;
	int nodos_normales = 0;

	for (unsigned int i = 0; i < nodos.size(); i++) {
		if (!nodos[i].is_stainer_node()) {
			nodos_normales++;
			centroide_x = centroide_x + nodos[i].get_coord_x();
			centroide_y = centroide_y + nodos[i].get_coord_y();
		}
	}

	centroide_x = centroide_x / nodos_normales;
	centroide_y = centroide_y / nodos_normales;

	double max_distancia = 0.0;

	vector<double> min_distancia;
	min_distancia.reserve(3);

	vector<double> distancias;
	distancias.reserve(nodos.size());

	for (unsigned int i = 0; i < nodos.size(); i++) {
		if (!nodos[i].is_stainer_node()) {
			double distancia;
			distancia = calcular_distancia(centroide_x, centroide_y, &nodos[i]);
			distancias.push_back(distancia);

			if (DEBUG) {
				cout << "[DEBUG] Distancia de centroide a " << i << " ("
						<< nodos[i].get_coord_x() << ", "
						<< nodos[i].get_coord_y() << ") = " << distancia
						<< endl;
			}

			if (distancia >= max_distancia) {
				max_distancia = distancia;
			}

			if (min_distancia.size() < 3) {
				min_distancia.push_back(distancia);
			} else {
				double max_distancia;
				max_distancia = 0.0;

				int max_distancia_index;
				max_distancia_index = 0;

				for (unsigned int j = 0; j < min_distancia.size(); j++) {
					if (max_distancia <= min_distancia[j]) {
						max_distancia = min_distancia[j];
						max_distancia_index = j;
					}
				}

				if (max_distancia > distancia) {
					min_distancia[max_distancia_index] = distancia;
				}
			}
		}
	}

	double max_min_distancia = 0.0;
	for (unsigned int i = 0; i < min_distancia.size(); i++) {
		if (min_distancia[i] >= max_min_distancia) {
			max_min_distancia = min_distancia[i];
		}
	}

	double radio_nodos_fijos = max_min_distancia + ((max_distancia
			- max_min_distancia) * multiplicador);

	if (DEBUG) {
		cout << "[DEBUG] Centroide (" << centroide_x << ", " << centroide_y
				<< ")" << endl;
		cout << "[DEBUG] Min distancia = " << max_min_distancia << endl;
		cout << "[DEBUG] Max distancia = " << max_distancia << endl;
		cout << "[DEBUG] Radio centroide = " << radio_nodos_fijos << endl;
	}

	for (unsigned int i = 0; i < nodos.size(); i++) {
		if (!nodos[i].is_stainer_node()) {
			if (distancias[i] <= radio_nodos_fijos) {
				nodos_fijos.push_back(i);
			}
		}
	}

	assert(nodos_fijos.size() >= 3);
}

void colgar_nodos(const vector<TSPNode> &nodos, const TSPCostMatrix &costos,
		const vector<unsigned int> &nodos_fijos, Solution &sol) {

	vector<unsigned int> nodos_a_colgar;

	if (DEBUG) {
		cout
				<< "[DEBUG] Listado de nodos que no estan en la solución y no son de Stainer: ";
	}
	for (unsigned int i = 0; i < nodos.size(); i++) {
		bool es_fijo;
		es_fijo = false;

		for (unsigned int j = 0; (j < nodos_fijos.size()) && !es_fijo; j++) {
			if (nodos_fijos[j] == i) {
				es_fijo = true;
			}
		}

		if ((!es_fijo) && (!nodos[i].is_stainer_node())) {
			nodos_a_colgar.push_back(i);

			if (DEBUG) {
				cout << i << " ";
			}
		}
	}
	if (DEBUG) {
		cout << endl;
	}

	vector<double> min_distancia;
	vector<unsigned int> min_distancia_index;

	for (unsigned int index = 0; index < nodos_a_colgar.size(); index++) {
		if (DEBUG) {
			cout << "[DEBUG] Procesando nodo a colgar <"
					<< nodos_a_colgar[index] << ">" << endl;
		}
		if (sol.get_links_count(nodos_a_colgar[index]) == 0) {
			min_distancia.clear();
			min_distancia_index.clear();

			for (unsigned int nodo_2n = 0; nodo_2n < nodos.size(); nodo_2n++) {
				if (nodos_a_colgar[index] != nodo_2n) {
					if (sol.get_links_count(nodo_2n) >= 2) {

						double distancia = 0.0;
						distancia = calcular_distancia(
								&nodos[nodos_a_colgar[index]], &nodos[nodo_2n]);

						if (min_distancia.size() < 3) {
							min_distancia.push_back(distancia);
							min_distancia_index.push_back(nodo_2n);
						} else {
							double max_min_distancia;
							int max_min_distancia_index;

							max_min_distancia = 0.0;
							max_min_distancia_index = 0;

							for (unsigned int j = 0; j < min_distancia.size(); j++) {
								if (max_min_distancia <= min_distancia[j]) {
									max_min_distancia = min_distancia[j];
									max_min_distancia_index = j;
								}
							}

							if (max_min_distancia > distancia) {
								min_distancia[max_min_distancia_index]
										= distancia;
								min_distancia_index[max_min_distancia_index]
										= nodo_2n;
							}
						}
					}
				}
			}

			int sorteo_index;
			sorteo_index = random_int(0, min_distancia.size() - 1);

			if (DEBUG) {
				cout << "[DEBUG] Se agregó el enlace ("
						<< nodos_a_colgar[index] << ", "
						<< min_distancia_index[sorteo_index] << ")" << endl;
			}

			sol.add_link(nodos_a_colgar[index],
					min_distancia_index[sorteo_index]);
		} else {
			if (DEBUG) {
				cout << "[DEBUG] El nodo <" << nodos_a_colgar[index]
						<< "> ya se encuentra conectado a la solución." << endl;
			}
		}
	}
}

void debugGradoDeNodos(const vector<TSPNode> &nodos, const Solution &sol) {
	cout << "==========================================" << endl;
	cout << "[DEBUG] Grado de los nodos de la solución:" << endl;

	for (unsigned int nodoIndex = 0; nodoIndex < nodos.size(); nodoIndex++) {
		if (nodos[nodoIndex].is_stainer_node()) {
			cout << "*";
		}
		cout << "Nodo " << nodoIndex << " (" << nodos[nodoIndex].get_coord_x()
				<< "," << nodos[nodoIndex].get_coord_y() << ") grado = "
				<< sol.get_links_count(nodoIndex) << endl;
	}
	cout << "==========================================" << endl;
}

void descomponerKeyPaths(const vector<TSPNode> &nodos, const Solution &Gsol,
		vector<TSPPath> &keyPaths, const TSPNode &nodoActual,
		TSPPath *caminoActual, set<int> &nodos_procesados) {

	if (caminoActual == NULL) {
		// Comienza la exploración de un nuevo camino.
		vector<unsigned int> nodos_adyacentes;
		Gsol.get_links(nodoActual.get_index(), nodos_adyacentes);

		nodos_procesados.insert(nodoActual.get_index());

		for (unsigned int i = 0; i < nodos_adyacentes.size(); i++) {
			caminoActual = new TSPPath(Gsol.get_costMatrix());
			caminoActual->add_initial_node(nodoActual.get_index());

			descomponerKeyPaths(nodos, Gsol, keyPaths,
					nodos[nodos_adyacentes[i]], caminoActual, nodos_procesados);

			delete caminoActual;
		}
	} else {
		// Ya se esta explorando un camino. Contínuo.
		bool is_endpoint_or_keynode = false;

		if (!nodoActual.is_stainer_node())
			is_endpoint_or_keynode = true;
		else if (Gsol.get_links_count(nodoActual.get_index()) >= 3)
			is_endpoint_or_keynode = true;

		if (is_endpoint_or_keynode) {
			if (nodos_procesados.find(nodoActual.get_index())
					== nodos_procesados.end()) {

				// Encontré un key-path!!!
				caminoActual->add_node(nodoActual.get_index());
				keyPaths.push_back(*caminoActual);

				// Podría continuar con la recursión, pero mejor dejarla por acá.
				// Aunque sea un poco más lento. Prefiero no arriesgarme a un
				// desborde de pila.
			}
		} else {
			// Es un nodos de Stainer.
			vector<unsigned int> nodos_adyacentes;
			Gsol.get_links(nodoActual.get_index(), nodos_adyacentes);

			int grado;
			grado = nodos_adyacentes.size();

			if (DEBUG) {
				cout << "[DEBUG] grado del nodo " << nodoActual.get_index()
						<< ": " << grado << endl;
			}

			if (grado == 2) {
				// Tiene grado 2. Puede ser parte de un keypath.
				caminoActual->add_node(nodoActual.get_index());

				if (!caminoActual->contains_node(nodos_adyacentes[0])) {
					descomponerKeyPaths(nodos, Gsol, keyPaths,
							nodos[nodos_adyacentes[0]], caminoActual,
							nodos_procesados);
				} else if (!caminoActual->contains_node(nodos_adyacentes[1])) {
					descomponerKeyPaths(nodos, Gsol, keyPaths,
							nodos[nodos_adyacentes[1]], caminoActual,
							nodos_procesados);
				}
			}
		}
	}
}

void descomponerKeyPaths(const vector<TSPNode> &nodos, const Solution &Gsol,
		const vector<TSPNode> &nodes_to_improve, vector<TSPPath> &keyPaths) {
	//	Def: key-path
	//	Es un path de Gsol cuyos extremos son nodos fijos o key-nodes y sus nodos inter-
	//	medios nodos no fijos y de grado 2.
	set<int> nodos_procesados;

	for (unsigned int i = 0; i < nodes_to_improve.size(); i++) {
		bool is_endpoint_or_keynode;
		is_endpoint_or_keynode = false;

		if (!nodes_to_improve[i].is_stainer_node())
			is_endpoint_or_keynode = true;
		else if (Gsol.get_links_count(nodes_to_improve[i].get_index()) >= 3)
			is_endpoint_or_keynode = true;

		if (is_endpoint_or_keynode) {
			if (nodos_procesados.find(nodes_to_improve[i].get_index())
					== nodos_procesados.end()) {

				descomponerKeyPaths(nodos, Gsol, keyPaths, nodes_to_improve[i],
						NULL, nodos_procesados);
			}
		}
	}
}

void subgrafoInducido(const vector<TSPNode> nodos, const TSPPath &keyPath,
		const Solution &notInSolution, Solution &HsolT) {

	vector<unsigned int> nodos_HsolT;

	for (unsigned int nodoIndex = 0; nodoIndex < nodos.size(); nodoIndex++) {
		if (notInSolution.get_links_count(nodoIndex) == 0) {
			nodos_HsolT.push_back(nodoIndex);
		}
	}

	if (DEBUG) {
		cout << "[DEBUG] Cantidad de nodos de Stainer del subgrafo inducido: "
				<< nodos_HsolT.size() << endl;
		for (unsigned int nodoIndex = 0; nodoIndex < nodos_HsolT.size(); nodoIndex++) {
			cout << nodos_HsolT[nodoIndex] << " ";
		}
		cout << endl << "[DEBUG] Key path: " << endl;
		keyPath.show();
		cout << endl;
	}

	for (unsigned int nodoIndex = 0; nodoIndex < keyPath.get_size(); nodoIndex++) {
		nodos_HsolT.push_back(keyPath.get_node_at(nodoIndex));
	}

	for (unsigned int origNodoIndex = 0; origNodoIndex < nodos_HsolT.size(); origNodoIndex++) {
		for (unsigned int destNodoIndex = 0; destNodoIndex < origNodoIndex; destNodoIndex++) {
			HsolT.add_link(nodos_HsolT[origNodoIndex],
					nodos_HsolT[destNodoIndex]);
		}
	}
}

void caminoMasCorto(const Solution &HsolT, const TSPPath &original,
		TSPPath &nuevo) {

	TSPPath* shortestPath;
	shortestPath = buscar_camino_en_sol(HsolT, original.get_node_at(0),
			original.get_node_at(original.get_size() - 1));

	nuevo = *shortestPath;
	delete shortestPath;
}

void localsearch1_2ns(const vector<TSPNode> nodos, Solution &Gsol,
		const vector<TSPNode> &nodes_to_improve) {
	vector<TSPPath> keyPaths;
	//	K(Gsol)=Descomposición de Gsol en key-paths;
	descomponerKeyPaths(nodos, Gsol, nodes_to_improve, keyPaths);

	if (DEBUG) {
		cout << "[DEBUG] Key paths encontrados:" << endl;
		for (unsigned int keyPathIndex = 0; keyPathIndex < keyPaths.size(); keyPathIndex++) {
			keyPaths[keyPathIndex].show();
		}
		cout << endl;
	}

	//  Hsol = Gsol
	//	foreach key-path p ∈ K(Gsol ) con extremos en u, v do
	//		H=el subgrafo inducido por NODOS(p) ∪ (SD \NODOS(Hsol));
	//		p el camino mas corto de u a v en H;
	//		Hsol=(Hsol \p) ∪ p;
	//	return Hsol;
	for (unsigned int keyPathIndex = 0; keyPathIndex < keyPaths.size(); keyPathIndex++) {
		Solution *HsolT;
		HsolT = new Solution(Gsol.get_costMatrix());
		subgrafoInducido(nodos, keyPaths[keyPathIndex], Gsol, *HsolT);

		TSPPath *pathNuevo;
		pathNuevo = new TSPPath(Gsol.get_costMatrix());
		caminoMasCorto(*HsolT, keyPaths[keyPathIndex], *pathNuevo);

		if (DEBUG) {
			cout << "[DEBUG] KeyPath Actual ";
			keyPaths[keyPathIndex].show();
			cout << " costo = " << keyPaths[keyPathIndex].get_path_cost()
					<< endl;
			cout << "[DEBUG] KeyPath Nuevo ";
			pathNuevo->show();
			cout << " costo = " << pathNuevo->get_path_cost() << endl;
		}

		if (keyPaths[keyPathIndex].get_path_cost() > pathNuevo->get_path_cost()) {
			Gsol.del_path(keyPaths[keyPathIndex]);
			Gsol.add_path(*pathNuevo);
		}

		delete pathNuevo;
		delete HsolT;

		if (DEBUG) {
			cout << "[DEBUG] Costo Solucion: " << Gsol.get_cost() << endl;
		}
	}
}

void obtenerKeyNodos(const Solution &sol, vector<TSPNode> &keyNodos) {
	//TODO: implementar!
}

void obtenerNodosNotIn(const vector<TSPNode> nodos, const Solution &sol,
		vector<TSPNode> nodosNotIn) {
	//TODO: implementar!!!
}

void obtenerKeyTree(const Solution &sol, int nodoRaiz, vector<TSPPath> keyTree) {
	//TODO: implementar!!!
}

void recconnect(Solution &sol, TSPNode &nodoRaiz,
		vector<TSPNode> &nodosDisponibles, bool &improve) {
	//TODO: implementar!!!
	//	Y ← N odos del Key Tree(v, Gsol );
	vector<TSPPath> keyTree;
	obtenerKeyTree(sol, nodoRaiz.get_index(), keyTree);

	//	Z ← Endpoints del Key Tree(v, Gsol );
	//	cost ← Costo del Key Tree(v, Gsol );

	//	H ← subgrafo inducido or (Y ∪ S) en GB ;
	//	H ← H\ARISTAS(Gsol (Z));
	//	T ← Z;
	//	value ← 0;
	//	mij ← FALSE, ∀i, j ∈ Z;
	//	while (∃ i, j ∈ Z /mij =FALSE) and (value < costs) do
	//	Elijo i, j ∈ Z en forma rand ́mica tal que mij = FALSE;
	//	o
	//	0 si (u, k) ∈ T ,

	//	Computo C con: cuk ←

	//	cuk en otro caso

	//	[valp , pij ] ← el camino mas corto desde i a j en H usando C;
	//	T ← T ∪ pij ;
	//	value ← value + valp ;

	//	Sea H ⊆ T la componente conexa que contiene a i;

	//	muk ← TRUE, ∀u, k ∈ (H ∩ Z);
	//	if (value < cost) then
	//	Gsol ← (Gsol \(Y \Z)) ∪ T ;
	//	improve ← TRUE;
	//	else improve ← FALSE ;
	//	return Gsol , improve;
}

void localsearch2_2ns(const vector<TSPNode> nodos, Solution &Gsol) {
	//	improve=TRUE;
	//	while improve do
	//		improve = FALSE;
	//		Sea X el conjunto de key-nodos de Gsol ;
	//		S = SD \ NODOS(Gsol);
	//		while not (improve) do
	//			Sea v ∈ X sin analizar;
	//			[Gsol , improve] = RecConnect(GB , C, Gsol , v, S);
	//	return Gsol ;

	bool improve = true;
	while (improve) {
		improve = false;

		vector<TSPNode> keyNodos;
		obtenerKeyNodos(Gsol, keyNodos);

		vector<TSPNode> nodosDisponibles;
		obtenerNodosNotIn(nodos, Gsol, nodosDisponibles);

		for (unsigned int keyNodoIndex = 0; (keyNodoIndex < keyNodos.size())
				&& !improve; keyNodoIndex++) {

			recconnect(Gsol, keyNodos[keyNodoIndex], nodosDisponibles, improve);
		}
	}
}

void localsearch(const int tid, unsigned int &cantidad_ejecuciones_busqueda1,
		double &mejora_acumulada_busqueda1,
		double &mejora_acumulada_porcentual_busqueda1,
		unsigned int &cantidad_ejecuciones_busqueda2,
		double &mejora_acumulada_busqueda2,
		double &mejora_acumulada_porcentual_busqueda2,
		const bool busqueda1habilitada, const bool busqueda2habilitada,
		const vector<TSPNode> nodos, Solution &solucion_asignada) {
	if (DEBUG) {
		cout << "[DEBUG] <thread:" << tid
				<< "> <BUSQUEDA LOCAL> Grado de los nodos en la solución original:"
				<< endl;
		debugGradoDeNodos(nodos, solucion_asignada);
	}

	double prob_aplicar_busqueda1 = PROBABILIDAD_BUSQUEDA_1;
	set<unsigned int> nodos_procesados_busqueda1;

	double prob_aplicar_busqueda2 = PROBABILIDAD_BUSQUEDA_2;
	set<unsigned int> nodos_procesados_busqueda2;

	bool mejorado;
	unsigned int max_improve_retry_times = BUSQUEDA_LOCAL_MAX_INTENTOS;
	unsigned int improve_retry_times = max_improve_retry_times;

	while (improve_retry_times > 0) {
		mejorado = false;

		if (busqueda1habilitada) {
			double costoOriginal;
			costoOriginal = solucion_asignada.get_cost();

			cout << "[DEBUG] <thread:" << tid
					<< "> <BUSQUEDA 1> Nodos a mejorar: ";
			vector<TSPNode> nodes_to_improve;
			for (unsigned int i = 0; i < nodos.size(); i++) {
				if (nodos_procesados_busqueda1.find(nodos[i].get_index())
						== nodos_procesados_busqueda1.end()) {

					if (random(0.0, 1.0) <= prob_aplicar_busqueda1) {
						nodes_to_improve.push_back(nodos[i]);
						cout << nodos[i].get_index() << " ";
					}
				}
			}
			cout << endl;

			if (nodes_to_improve.size() > 0) {
				cout << "[DEBUG] <thread:" << tid
						<< "> <BUSQUEDA 1> Costo original: " << costoOriginal
						<< endl;

				localsearch1_2ns(nodos, solucion_asignada, nodes_to_improve);

				cout << "[DEBUG] <thread:" << tid
						<< "> <BUSQUEDA 1> Costo mejorado: "
						<< solucion_asignada.get_cost() << endl;

				double mejora_busqueda;
				mejora_busqueda = costoOriginal - solucion_asignada.get_cost();

				mejora_acumulada_busqueda1 += mejora_busqueda;
				mejora_acumulada_porcentual_busqueda1 += (mejora_busqueda * 100
						/ costoOriginal);
				cantidad_ejecuciones_busqueda1++;
				mejorado = mejorado || (mejora_busqueda > 0.0);

				if (DEBUG) {
					cout << "[DEBUG] <thread:" << tid
							<< "> <BUSQUEDA 1> mejora_busqueda = "
							<< mejora_busqueda << ", mejorado = " << mejorado
							<< endl;
				}
			} else {
				cout << "[DEBUG] <thread:" << tid
						<< "> <BUSQUEDA 1> Sin nodos para mejorar." << endl;
			}

			if (!mejorado) {
				for (unsigned int i = 0; i < nodes_to_improve.size(); i++) {
					nodos_procesados_busqueda1.insert(
							nodes_to_improve[i].get_index());
				}
			}
		}

		if (busqueda2habilitada) {

		}

		if (mejorado) {
			improve_retry_times = max_improve_retry_times;
			nodos_procesados_busqueda1.clear();
			nodos_procesados_busqueda2.clear();
		} else {
			if (((!busqueda1habilitada) || (nodos_procesados_busqueda1.size()
					== nodos.size())) && ((!busqueda2habilitada)
					|| (nodos_procesados_busqueda2.size() == nodos.size()))) {
				// No queda nada por hacer.
				improve_retry_times = 0;
			} else {
				improve_retry_times--;
			}
		}
	}
}

int main(int argc, char **argv) {
	// CONFIGURACIÓN DEL ALGORITMO =========================================
	cout << "[INFO] DEBUG: " << DEBUG << endl;
	cout << "[INFO] RANDOM_SEED: " << RANDOM_SEED << endl;
	cout << "[INFO] K_CAMINOS_MAS_CORTOS: " << K_CAMINOS_MAS_CORTOS << endl;
	cout << "[INFO] CANTIDAD_DE_SOLUCIONES POR DEFECTO: "
			<< CANTIDAD_DE_SOLUCIONES << endl;
	cout << "[INFO] CANTIDAD_NODOS_STAINER_MIN: " << CANTIDAD_NODOS_STAINER_MIN
			<< endl;
	cout << "[INFO] CANTIDAD_NODOS_STAINER_MAX: " << CANTIDAD_NODOS_STAINER_MAX
			<< endl;
	cout << "[INFO] COMP_CONEXA_MIN_SIZE: " << COMP_CONEXA_MIN_SIZE << endl;
	cout << "[INFO] COMP_CONEXA_MAX_SIZE: " << COMP_CONEXA_MAX_SIZE << endl;
	cout << "[INFO] MANTENER_DESIGUALDAD_TRIANGULAR: "
			<< MANTENER_DESIGUALDAD_TRIANGULAR << endl;
	cout << "[INFO] PROBABILIDAD_BUSQUEDA_1: " << PROBABILIDAD_BUSQUEDA_1 << endl;
	cout << "[INFO] PROBABILIDAD_BUSQUEDA_2: " << PROBABILIDAD_BUSQUEDA_2 << endl;
	cout << "[INFO] BUSQUEDA_LOCAL_MAX_INTENTOS: " << BUSQUEDA_LOCAL_MAX_INTENTOS << endl;

	if (argc < 2) {
		cout << "Sintaxis: " << argv[0]
				<< " <instancia> [busq 1] [busq 2] [seed] [# soluciones]"
				<< endl;
		exit(-1);
	}

	// INSTANCIACIÓN DEL PROBLEMA ==========================================
	string instance_file_path;
	instance_file_path = argv[1];
	cout << "[INFO] Input file: " << instance_file_path << endl;

	bool busqueda1habilitada = true;
	bool busqueda2habilitada = true;

	if (argc >= 3) {
		busqueda1habilitada = (string(argv[2]) == "1");

		if (argc >= 4) {
			busqueda2habilitada = (string(argv[3]) == "1");
		}
	}
	cout << "[INFO] Búsqueda 1: " << busqueda1habilitada << endl;
	cout << "[INFO] Búsqueda 2: " << busqueda2habilitada << endl;

	long seed = 1;
	if (argc >= 5) {
		seed = strtol(argv[4], NULL, 10);
	} else {
		if (RANDOM_SEED) {
			seed = time(NULL);
		}
	}
	srand(seed);
	cout << "[INFO] Current seed: " << seed << endl;

	int cantidad_soluciones;
	if (argc >= 6) {
		cantidad_soluciones = strtol(argv[5], NULL, 10);
	} else {
		cantidad_soluciones = CANTIDAD_DE_SOLUCIONES;
	}
	srand(seed);
	cout << "[INFO] Cantidad de soluciones: " << cantidad_soluciones << endl;

	// Cargo el archivo de instancias.
	vector<TSPNode> nodos;
	if (load_instance(instance_file_path, nodos) != EXIT_SUCCESS) {
		puts("[ERROR] Ocurrió un error cargando el archivo de instancias.");
		return EXIT_FAILURE;
	}

	// Muestro los nodos cargados.
	for (unsigned int i = 0; i < nodos.size(); i++) {
		TSPNode *node;
		node = &(nodos[i]);

		cout << "[INFO] " << node->get_id() << " (" << node->get_coord_x()
				<< "," << node->get_coord_y() << ")" << endl;
	}

	// Agrego nodos de Stainer.
	int cant_nodos_stainer = (int) (random(CANTIDAD_NODOS_STAINER_MIN,
			CANTIDAD_NODOS_STAINER_MAX) * nodos.size());
	generate_stainer_nodes(nodos, cant_nodos_stainer,
			MANTENER_DESIGUALDAD_TRIANGULAR);
	cout << "[INFO] Se generaron " << cant_nodos_stainer
			<< " nodos de Stainer." << endl;

	// Calculo los costos entre nodos.
	TSPCostMatrix costos(nodos.size());
	if (calculate_costs(nodos, costos) != EXIT_SUCCESS) {
		puts("[ERROR] Ocurrió un error calculando los costos.");
		return EXIT_FAILURE;
	}

	cout << "[INFO] Cantidad máxima de hilos: " << omp_get_max_threads() << endl;
	int tid;

	vector<Solution> soluciones_finales;
	queue<Solution> soluciones_construidas;

	int aux_cantidad_construcciones_asignadas;
	aux_cantidad_construcciones_asignadas = 0;

	int aux_cantidad_busquedas_asignadas;
	aux_cantidad_busquedas_asignadas = 0;

	bool trabajo_terminado;
	bool tiene_construccion_asignada;
	bool tiene_solucion_asignada;

	Solution solucion_asignada;

	unsigned int global_cantidad_ejecuciones_busqueda1 = 0;
	double global_mejora_acumulada_busqueda1 = 0.0;
	double global_mejora_porcentual_acumulada_busqueda1 = 0.0;
	unsigned int global_cantidad_ejecuciones_busqueda2 = 0;
	double global_mejora_acumulada_busqueda2 = 0.0;
	double global_mejora_porcentual_acumulada_busqueda2 = 0.0;

	unsigned int cantidad_ejecuciones_busqueda1 = 0;
	double mejora_acumulada_busqueda1 = 0.0;
	double mejora_porcentual_acumulada_busqueda1 = 0.0;
	unsigned int cantidad_ejecuciones_busqueda2 = 0;
	double mejora_acumulada_busqueda2 = 0.0;
	double mejora_porcentual_acumulada_busqueda2 = 0.0;

	/* Fork a team of threads with each thread having a private tid variable */
#pragma omp parallel default(shared) private(tid, trabajo_terminado, solucion_asignada, tiene_construccion_asignada, tiene_solucion_asignada, cantidad_ejecuciones_busqueda1, cantidad_ejecuciones_busqueda2, mejora_acumulada_busqueda1, mejora_acumulada_busqueda2, mejora_porcentual_acumulada_busqueda1, mejora_porcentual_acumulada_busqueda2)
	{
		trabajo_terminado = false;
		tid = omp_get_thread_num();

		while (!trabajo_terminado) {
			tiene_solucion_asignada = false;
			tiene_construccion_asignada = false;

#pragma omp critical (asignacion_trabajo)
			{
				if (aux_cantidad_busquedas_asignadas < cantidad_soluciones) {
					if (soluciones_construidas.empty()) {
						if (aux_cantidad_construcciones_asignadas
								< cantidad_soluciones) {
							cout << "[INFO<thread:" << tid
									<< ">] Toca construir." << endl;
							aux_cantidad_construcciones_asignadas++;
							tiene_construccion_asignada = true;
						} else {
							trabajo_terminado = true;
						}
					} else {
						cout << "[INFO<thread:" << tid
								<< ">] Toca búsqueda local." << endl;
						aux_cantidad_busquedas_asignadas++;

						tiene_solucion_asignada = true;
						solucion_asignada = soluciones_construidas.front();
						soluciones_construidas.pop();
					}
				} else {
					trabajo_terminado = true;
				}
			}

			if (tiene_construccion_asignada) {
				// ALGORITMO DE CONSTRUCCIÓN ==========================================
				// Selección de los nodos fijos.
				vector<unsigned int> nodos_fijos;
				calcular_nodos_fijos(nodos, costos, nodos_fijos, random(
						COMP_CONEXA_MIN_SIZE, COMP_CONEXA_MAX_SIZE));
				if (DEBUG) {
					cout << "[DEBUG] Nodos fijos: ";
					for (unsigned int i = 0; i < nodos_fijos.size(); i++) {
						cout << nodos_fijos[i] << "  ";
					}
					cout << endl;
				}

				// Creación de la solución vacía.
				Solution nueva_solucion(costos);

				// Construcción de la componente 2N-conexa.
				constphase2_2NS(costos, nodos_fijos, nueva_solucion);

				// Se completa la solución inicial colgado los nodos restantes de la 2N-conexa.
				colgar_nodos(nodos, costos, nodos_fijos, nueva_solucion);

#pragma omp critical (construccion)
				{
					cout << "[INFO<thread:" << tid
							<< ">] Nueva solución construida (Costo: "
							<< nueva_solucion.get_cost() << ")." << endl;
					soluciones_construidas.push(nueva_solucion);
				}
			}

			if (tiene_solucion_asignada) {
				// ALGORITMO DE BÚSQUEDA LOCAL ==========================================
				cantidad_ejecuciones_busqueda1 = 0;
				mejora_acumulada_busqueda1 = 0.0;
				mejora_porcentual_acumulada_busqueda1 = 0.0;

				cantidad_ejecuciones_busqueda2 = 0;
				mejora_acumulada_busqueda2 = 0.0;
				mejora_porcentual_acumulada_busqueda2 = 0.0;

				localsearch(tid, cantidad_ejecuciones_busqueda1,
						mejora_acumulada_busqueda1,
						mejora_porcentual_acumulada_busqueda1,
						cantidad_ejecuciones_busqueda2,
						mejora_acumulada_busqueda2,
						mejora_porcentual_acumulada_busqueda2,
						busqueda1habilitada, busqueda2habilitada, nodos,
						solucion_asignada);

#pragma omp critical (busqueda_local)
				{
					global_cantidad_ejecuciones_busqueda1
							+= cantidad_ejecuciones_busqueda1;
					global_mejora_acumulada_busqueda1
							+= mejora_acumulada_busqueda1;
					global_mejora_porcentual_acumulada_busqueda1
							+= mejora_porcentual_acumulada_busqueda1;

					global_cantidad_ejecuciones_busqueda2
							+= cantidad_ejecuciones_busqueda2;
					global_mejora_acumulada_busqueda2
							+= mejora_acumulada_busqueda2;
					global_mejora_porcentual_acumulada_busqueda2
							+= mejora_porcentual_acumulada_busqueda2;

					cout << "[INFO<thread:" << tid
							<< ">] Solución final agregada." << endl;
					soluciones_finales.push_back(solucion_asignada);
				}
			}
		}
	} /* end of parallel section */

	// Presentación de las soluciones ====================================================

	cout
			<< "[ SOLUCIONES ENCONTRADAS DEL PROBLEMA =============================== ]"
			<< endl;

	cout << endl << "Detalle de las soluciones: " << endl;
	for (unsigned int i = 0; i < soluciones_finales.size(); i++) {
		cout << "[ SOLUCION " << i << "]" << endl;
		soluciones_finales[i].show();
	}

	cout << "Cantidad de soluciones: " << soluciones_finales.size() << endl
			<< endl;

	if (busqueda1habilitada) {
		cout << "Total mejora búsqueda local 1: "
				<< global_mejora_acumulada_busqueda1 << endl;
		cout << "Mejora promedio búsqueda local 1: "
				<< global_mejora_acumulada_busqueda1
						/ global_cantidad_ejecuciones_busqueda1 << endl;
		cout << "Mejora porcentual promedio búsqueda local 1: "
				<< global_mejora_porcentual_acumulada_busqueda1
						/ global_cantidad_ejecuciones_busqueda1 << "%" << endl;
	}

	if (busqueda2habilitada) {
		cout << "Total mejora búsqueda local 2: "
				<< global_mejora_acumulada_busqueda2 << endl;
		cout << "Mejora promedio búsqueda local 2: "
				<< global_mejora_acumulada_busqueda2
						/ global_cantidad_ejecuciones_busqueda2 << endl;
		cout << "Mejora porcentual promedio búsqueda local 2: "
				<< global_mejora_porcentual_acumulada_busqueda2
						/ global_cantidad_ejecuciones_busqueda2 << "%" << endl;
	}
	cout << endl;

	double costo_acumulado = 0.0;
	int mejor_sol_index = 0;

	for (unsigned int i = 0; i < soluciones_finales.size(); i++) {
		if (soluciones_finales[mejor_sol_index].get_cost()
				> soluciones_finales[i].get_cost()) {
			mejor_sol_index = i;
		}
		cout << "[SOLUCION " << i << "] " << soluciones_finales[i].get_cost()
				<< endl;
		costo_acumulado += soluciones_finales[i].get_cost();
	}

	double costo_promedio = costo_acumulado / soluciones_finales.size();
	double stdev = 0.0;

	if (soluciones_finales.size() > 1) {
		double stdev_aux = 0.0;
		for (unsigned int i = 0; i < soluciones_finales.size(); i++) {
			stdev_aux += pow(soluciones_finales[i].get_cost() - costo_promedio,
					2);
		}
		stdev = sqrt((1.0 / (soluciones_finales.size() - 1.0)) * stdev_aux);
	}

	cout << "Costo mejor solución: " << soluciones_finales[mejor_sol_index].get_cost() << endl;
	cout << "Costo promedio de las soluciónes: " << costo_promedio << endl;
	cout << "Desviación estándar: " << stdev << endl;

	return EXIT_SUCCESS;
}
